Creating Demos - Coder Tutorial #7
[3D Worlds]
By Polaris
Greetings to all you demo coders out there! I hope everyone is healthy and happy,
and enjoying their coding projects!
For this issue I've decided to discuss three dimensional mathematics and how basic "3d"
is achieved. Many people tend to "gloss this over" - because they don't feel that they
need to fully understand it. There are countless postings in forums from people that
are struggling with "gotchas" in Direct X and openGL because they have neglected to master
the basics. Let's master these basics and avoid future struggles!
In this tutorial I'll be teaching you to make wire frame renderings. We'll do the
math ourselves, with basic trigonometry. If you understood my last tutorial,
you are in good shape. If you didn't follow my last tutorial, have a look!
You can also use this refresher on the web: "Trigonometry: A Crash Review".
Check it out here: http://www.zaimoni.com/Trig.htm. As usual, we'll be using Dev C++
and Allegro. Look at older tutorials for refreshers.
With every tutorial, feel free to me questions directly if something doesn't make sense:
Polaris@northerndragons.ca.
Don't forget to tell me what you would like the next tutorial to be. I can't meet
everyone's needs - but I'll certainly try to.
Wireframe Worlds - Cartesian Coordinate Systems (2d)
The Cartesian Coordinate system was developed by the French mathematician René Descartes.
It's rumored that he was sick in bed and was watching a fly buzzing around his ceiling
made of tiles. He didn't have the strength to move to swat it; so he noticed that he
could the count tiles from a specific tile (up/down and left to right) and remember
where the fly was to kill it in the morning. You can imagine pirates doing the same thing
with a land marker. "YAARRGH: From the scull rock, the treasure is 2 paces north, and
5 paces east". The origin is the center of where we start measuring from (in that case
the scull rock).
While we don't have evidence that it was a fly that inspired his mathematics - Decartes'
contribution in 1637 was enormous. It's this contribution that all three dimensional
mathematics is based upon, and gave birth to analytic geometry.
While it should be review for everyone.. here are the basics of the two dimensional
Cartesian coordinate system. The idea is to divide motion into two components.
These are called axes. This is similar to a computer screen - where you have
Screen X (left to right) and Screen Y (up and down). Each axis is like a ruler;
measuring distance along that axis. Every point can be represented by its X value
and Y value. You intersect the two X,Y values - and you know exactly where the point
(or fly) lies. This pair of values is called a coordinate.
The computer screen co-ordinates are setup slightly differently than their
mathematical pure counterpart. In computer graphics the origin at (0,0) is typically
the upper left of the screen, whereas in mathematics - the origin is in the center.
In screen units, as you grow in Y co-ordinates... your Y value goes "down" the screen...
which is exactly opposite to the conventional Y axis in mathematics (upside down).
In the end, this will mean that we'll have to transform our mathematics to the
"screen coordinate system". Usually this is the very last step of any 3d application.
We've already done screen coordinate transformation in the last tutorial on lenses.
Points? It's all about Points? What's the Point????
So far, I've made a big deal about points. This might seem very trivial, but it's not.
Objects in our three dimensional world - can be represented by points!
Imagine a cube a moment. A cube has eight outside edges - where its surface comes to
a "point". When we sketch out a cube - we imagine these points connected with lines.
This type of basic rendering is called wire frame (as shown in the picture).
You should realize that we aren't drawing just any lines. Instead we are connecting lines
that are part of the same surface (same shape). In the image, you can see a "cube", as we
normally think about.. and a weird object that shares the same points, but is connected
in an arbitrary way. So, it's not just about points, but putting those points together
as part of a surface.
Any three dimensional surface can be approximated by putting together flat shapes.
This is like Origami (the art of Japanese paper folding). To make a cube, we take
six square shapes and arrange them to form the cube. For a three sided pyramid, we
take 4 triangle shapes (one for the bottom) and arrange them to form a pyramid.
These flat shapes are generically called polygons, and can be any shape (triangle, square,
hexagon). The strictest definition would say - a polygon is a flat shape bounded
by straight lines.
You could render a filled cube (not wire frame) by drawing the six sides (squares) of
the cube and filling them in. This would look similar to old style polygon graphics of
the 1980's. Right now we are doing the same thing, but we aren't bothering to fill our
shapes in. Each of the six sides equates to a single polygon. For now, we'll focus on
just defining wire frame objects and rendering them so they look proper.
We can't represent these points mathematically, unless we have some way to measure them.
This is what coordinates are used for. Later on we can take the coordinates of an object
(like our cube), and rotate them; move them around etc (by using basic math). This is what
enables us to have virtual universes in our computer games and consoles.
Extending into the Third Dimension (Which way is Z?)
Descartes Coordinate system was first envisioned as a two dimensional one.
An easy extension however is to add another measuring stick - the Z axis.
With X,Y, and Z... we can represent any three dimensional point.
These equate to (from a viewer position) - left and right, up and down,
and forward and backward. You can imagine a string hung from Descartes' ceiling,
with markings at the same length as the ceiling tile. This would allow him to
measure how far down the fly was hovering from the ceiling. You would need the
position of the fly in relation to the three axis: X (left, right), Y (up, down),
Z (forward and backward). Our three dimensional origin then becomes (0,0,0).
Oddly enough, mathematics never fully standardized (in my belief) which way "Z"
is measured. If you are holding a coordinate system directly in front of
you, looking towards origin.... does Z increase as you walk forward, or does it
increase as you walk backward? It turns out that this was never fully decided.
Mathematicians found each definition useful in some cases. Instead of forcing
a standard, they came up with two coordinate systems. (Making each a standard.).
The left-handed coordinate system works like this. You take your left hand,
with your palm facing upwards. You point your fingers in the direction of the
positive X axis (to the right). You curl your fingers into the direction of the
positive y-axis (up). Your thumb now points in the direction of the positive Z axis.
This means that Z grows as we "walk forward".
The right-handed coordinate system works almost the same way. You take your
right hand, with your palm facing upwards. Again, you point your fingers
in the direction of the positive X axis (right) and then curl them to the
positive y-axis (up). Your thumb now points in the positive Z axis.
With the right handed system... Z grows as we "walk backward".
To add even more hilarity, computer graphics API's couldn't decide on a
coordinate system (right or left) to be standard either. Open GL uses a
right-handed coordinate system, while Direct X uses a left-handed coordinate system.
I'm going to use the left-handed system for the remainder of the tutorial.
This means that point <0,0,-10> is in front of the origin, while point <0,0,10> is
behind it. I realize this is confusing now, but as we work with it - it should make
more sense.
Transferring to Screen Coordinates (Revisited)
I mentioned above that the computer's origin system starts at the top left
of the screen, at coordinates (0,0). X grows from left to right, which
matches our pure mathematical definition; but Y is upside down (growing as
you go down). We did some screen coordinate conversion in the lens tutorial,
but let's define it here more generally.
The most fundamental thing we need to do is move the origin. The important thing
to remember is that the origin can be anywhere we want it to be. It's the one thing
that's stationary - the "skull rock" that the pirate assumes won't move. We need to
adjust the origin in our math coordinates to be the center of our screen coordinates.
In mode 13h, the center of the screen is (160,100). For us to do this on demand,
we'll use the following equations:
screen_x = pure_x + x_origin_offset
screen_y = -pure_y + y_origin_offset
We'll define our x_origin_offset to have a value of 160 (for mode 13h),
and the y_origin_offset to have a value of 100.
Shapes and Objects - Getting Curvy.
So far we've shown how a cube can be composed from points - which make up surfaces.
In other words, we can build a cube from squares, and squares from points.
You might think that this means that we can only render sharp shaped objects
with our system. How do you make a curve with only points and straight lines?
The trick is, that you don't. It's impossible to truly represent a curve with
points connected by straight lines. Instead, we do the best we can by adding
more points and lines to approximate the curve. The more points we add along the
surface of the curve, the better our shape will appear. You can see this with the
shapes that approximate a sphere. In the low polygon sphere, we've only got
3 shapes (or polygons) visible, that give it a "curvy" look. In the higher polygon
sphere, we've added more shapes, points and lines. As we continue to add more polygons,
the sphere becomes more and more defined.
Project #1 - Kicking it 2d
For our first project we'll manipulate a simple two dimensional shape. We'll start with
a square and convert it from pure mathematical co-ordinates to screen coordinates.
After that we'll extend it to perform some basic operations on the points.
Our first project objectives include:
1. Defining a object points.
2. Converting the co-ordinates to screen coordinates.
3. Drawing the object on the screen.
Similar to my last tutorial, we'll start with an basic framework. If you haven't seen
the framework before or are unsure - review the previous articles. You can get
the framework in zip format: wireframe.a.rar in the bonus pack. We will apply our changes to Wireframe.a,
step by step. You'll notice I'm using rar files, which are just like zip files.
To extract them you can download winrar from http://www.rarlab.com/.
1. We'll start by adding our x_origin and y_origin to the code.
I've done this with a pair of #defines, just under our #define's for
sceen_x/screen_y:
#define x_origin_offset 160
#define y_origin_offset 100
2. Following that we need to define a structure to hold our vertices.
We do that just under our #defines:
typedef struct
{
float x;
float y;
} Vector2d;
3. At this point we'll add a routine to draw a Wireframe polygon. Let's write the
DrawScreenCords2d routine. It will take a bitmap object (to plot on),
a Vector2d array (what to plot), a colour (how to plot it), and a total # of points
(how many to plot). It will draw a bounded shape of lines for all points.
At the end it will connect the last point to the first point,
a feat achieved using the modulus operator. As screen coordinates are integers,
I've typecast them to integers from floats. (truncating them to screen coordinates).
// converts mathematical points to screen points and plots them.
void DrawScreenCords2d(BITMAP *bitmap,Vector2d *inPoints,int total,int colour)
{
int i;
// draw our shape. Notice this is a closed shape, so point a connects to
// point b, point b connects to point c, and point c - connects to point a.
for (i=0;i<total;i++)
{
line(bitmap,
(int)(inPoints[i].x+x_origin_offset),
(int)(-inPoints[i].y+y_origin_offset),
(int)(inPoints[(i+1)%total].x+x_origin_offset),
(int)(-inPoints[(i+1)%total].y+y_origin_offset),
255);
}
}
4. Now we need to add our points to the main routine. I've done that right
at the beginning. Notice I'm also adding the variable lOffScreen to hold the
double buffer.
// main constants (more next phase)
Vector2d lSquarePoints[4]=
{
{20,20}, // top right
{-20,20}, // top left
{-20,-20}, // bottom left
{20,-20} // bottom right
}; // square points
BITMAP *lOffScreen; // off screen buffer
5. Now that we've allocated our points, we need to draw them in our render loop.
We also need to allocate and destroy our off screen render surface. This is added
as follows.
// init more stuff (next phase)
lOffScreen = create_bitmap(screen_x, screen_y); // NEW
while ((!key[KEY_ESC])&&(!key[KEY_SPACE]))
{
// DO SOMETHING AMAZING HERE!
clear_bitmap(lOffScreen); //NEW
DrawScreenCords2d(lOffScreen, lSquarePoints,4,255);
blit(lOffScreen, screen, 0, 0, 0, 0, screen_x, screen_y); // NEW
};
// de-init more stuff (next phase)
destroy_bitmap(lOffScreen);
Provided that everything goes according to plan - we should now be able to
compile the code - and enjoy our first Wireframe rendering!
Transformations - Introducing SRT
So far we've been able to create a beautiful square... that does noting
except exhibit perfect square-ness. It would be far more interesting if
we could get our square to do things. There are three fundamental transformations
for all objects - Translation, Scaling and Rotation. (also known as S.R.T).
I'll define each one in turn, show the mathematics used for achieving the effect
and extend our square wireframe program to really dance. We will start with
Translation because it's the simplest transformation.
Translation - The T in SRT
Translating an object - essentially means to move it. If we wanted to move
our square upwards for example, we'd simply add some value to the Y components
of our vertices. Notice I said add, not subtract. Remember that we are dealing
with mathematics at this point and not screen coordinates. Our translation
can also go in the X direction. Because of this, translations are often represented
as a pair of values (for 2d objects), or three values (for 3d objects). Our formula
for translation appears as follows:
new_x = old_x + translation_x
new_y = old_y + translation_y
(and similarly for 3d)
new_z = old_z + translation_z
Let's add translation to our program - step by step:
1. Our first step is to add a translation routine. I've done this just above the
drawing routine.
// At this point I'm doing just floats. This is because the convert to int
// occurs at the time of drawing.
void Translate2d(Vector2d *inPoints,Vector2d *outPoints,int Total,
float xTrans,float yTrans)
{
int i;
for (i=0;i<Total;i++)
{
outPoints[i].x=inPoints[i].x+xTrans;
outPoints[i].y=inPoints[i].y+yTrans;
}
}
2. Now that we have the code to translate our points, we need to make use of it.
The first thing we need to do is introduce some variables:
Vector2d lTranslatedPoints[4]; // translated points
float x_pos; // object translation
float y_pos;
3. We also need to set our x_pos and y_pos to an intial value. I've done that right
under the create_bitmap used for the off screen buffer.
x_pos=0;
y_pos=0;
4. Our main render loop changes as follows:
while ((!key[KEY_ESC])&&(!key[KEY_SPACE]))
{
// DO SOMETHING AMAZING HERE!
clear_bitmap(lOffScreen);
// adjust SRT's depending on keys
if (key[KEY_UP]) y_pos++; // TRANSLATE
if (key[KEY_DOWN]) y_pos--;
if (key[KEY_LEFT]) x_pos--;
if (key[KEY_RIGHT]) x_pos++;
Translate2d(lSquarePoints,lTranslatedPoints,4,x_pos,y_pos);
DrawScreenCords2d(lOffScreen, lTranslatedPoints,4,255);
blit(lOffScreen, screen, 0, 0, 0, 0, screen_x, screen_y);
rest(10); // prevents it from flying off the screen too FAST
};
5. Voila. Our cursor keys are queried by the if statements, adjusting the y_pos
and x_pos variables. The lSquarePoints are translated by Translate2d, and the
results are stored into lTranslatedPoints.
Scaling - The S in SRT
Scaling an object isn't much different from translating it. With scaling, instead of
moving an object by X,Y or Z values - we stretch (or compress) an object in X,Y,Z
values. We do this with a scaling factor. Scaling an object by 0.5 will shrink
it by a half, scaling by 1.0 will remain the same, and scaling by 2.0 will double
the object. When I say "double / half etc".. I'm referring to the distance
between our vertices. Remember we don't have to scale an object in all three dimensions
simultaneously; it's possible for us to scale our square by different values for
the axis - creating rectangles or other alternate shapes. Scaling is most often thought
of as a general object modifier (changing height, width and breadth simultaneously), and
we'll code it just like that.
new_x = old_x * scale_x
new_y = old_y * scale_y
(and similarly for 3d)
new_z = old_z * scale_z
At this point we'll code our scaling routine. We will also combine it with the
translated values, allowing us to scale and translate our object. Our changes will
look very similar to our translation code, with only a few exceptions.
1. Our first step is to add our scaling routine.
void Scale2d(Vector2d *inPoints,Vector2d *outPoints,int Total,float scale);
{
int i;
for (i=0;i<Total;i++)
{
outPoints[i].x=inPoints[i].x*scale;
outPoints[i].y=inPoints[i].y*scale;
}
}
2. We'll add another set of variables to allow us to scale our points.
To make it clear:
Vector2d lTranslatedPoints[4]; // translated points
BECOMES:
Vector2d lTranslatedAndScaledPoints[4]; // translated and scaled points
and we add:
Vector2d lScaledPoints[4]; // translated points
float scale; // object scale
3. We need to initialize our scale (at the same place that we initialize x_pos and y_pos).
x_pos=0;
y_pos=0;
scale=1; // notice it's one (== no change)
4. Our main render loop changes as follows:
while ((!key[KEY_ESC])&&(!key[KEY_SPACE]))
{
// DO SOMETHING AMAZING HERE!
clear_bitmap(lOffScreen);
// adjust SRT's depending on keys
if (key[KEY_UP]) y_pos++; // TRANSLATE
if (key[KEY_DOWN]) y_pos--;
if (key[KEY_LEFT]) x_pos--;
if (key[KEY_RIGHT]) x_pos++;
if (key[KEY_Q]) scale+=0.1; // scale
if (key[KEY_A]) scale-=0.1;
if (scale<0) scale=0; // prevents scaling with - number
Scale2d(lSquarePoints,lScaledPoints,4,scale); // scale
Translate2d(lScaledPoints,lTranslatedAndScaledPoints,4,x_pos,y_pos);
DrawScreenCords2d(lOffScreen, lTranslatedAndScaledPoints,4,255);
blit(lOffScreen, screen, 0, 0, 0, 0, screen_x, screen_y);
rest(10); // prevents it from flying off the screen too FAST
};
5. Voila! Our q and a keys now scale our object, and our cursor keys now allow us
to translate it.
Rotation - The R in SRT
Rotation is our most difficult transformation. While I'll explain how the
rotation formulas work on the inside, you don't need to understand them to make use of them.
Remember, all we need to do is think in terms of points - lines and surfaces will follow.
To make things even simpler, I'll focus on top down rotations (just like our 2d graphics
here).
Rotations are defined by two fundamental things. The pivot point (where we are rotating),
and the degree of rotation. As we'll need to use trigonometry to calculate our
rotations - our degrees will not be in angles... but instead will be in radians.
Radians are just another unit of measure of angle. Radians are based on the value of PI.
In radians, PI represents a 180 degree rotation. Similarly, 1/2 PI is a 90 degree
rotation. Imagine this to be just the same as exchanging currencies. One currency
is called degrees, and the other is called radians. 180 degrees is roughly 3.14 Radians
(a truncated value of PI).
We can convert between radians and degrees as follows
Radian = (Degree / 360) * 2PI
Degree = (Radian / 2PI) * 360.
(Where 2PI == something like 6.28).
Now, to simplify matters - we are going to develop our formulas with the pivot point
at the origin. This doesn't change our capabilities, if we wanted to develop a rotation
formula to have an arbitrary pivot point, we still can. In that situation we'd use
translation to move the pivot point to our origin, perform the rotation, and then reverse
the translation to move everything back to the pivot point. Since our simplification
doesn't change our capabilities - we'll setup our formulas to pivot around the origin.
Our first rotation formula will be the standard 2d rotation. We will consider each rotation
in terms of axis. To start with, we'll define a Z rotation - which is the standard rotation
for a top down / traditional 2d view. It's like someone glued our object to the Z axis
and then twisted the Z axis by the degrees desired. Our other rotations will be for
the X and Y axes respectively. Let's define our rotation formulas.
Aside: For those familiar with my articles in Hugi - the following definitions
will seem very familiar. They should - because they are identical to my Article in Hugi 27
(Sphere Tessellation 101: "The Art of Making Spheres out of Triangles"). If you are
interested in seeing another application of these formulas (to build spheres etc) - check it
out. Diskmag version: http://hugi.scene.org/fate.php?page=hugi27).
For each rotation around an axis, there are two equations. There isn't a third equation,
as when you rotate around an axis, your value for that axis (x,y,z) does not change.
For example, your Z value for a point will not change if you rotate a point around the
Z axis. Etc.
Here the following formulas:
Z Axis Rotation
New_X = x * cos(z_angle) - y * sin(z_angle)
New_Y = y * cos(z_angle) + x * sin(z_angle)
X Axis Rotation
New_Y = y * cos(x_angle) - z * sin(x_angle)
New_Z = y * sin(x_angle) + z * cos(x_angle)
Y Axis Rotation
New_Z = z * cos(y_angle) - x * sin(y_angle)
New_X = z * sin(y_angle) + x * cos(y_angle)
Did you take my word on it? I didn't think so. So, let's look at one of these in detail.
Just realize that all you need is to know how to apply the formulas.
Knowing how it works is just a bonus.
In the diagram, we are rotating point X,Y by angle B. We start however at angle a.
Now, let me introduce some trigonometric identities. [Take my word on these okay?].
cos(a+b) = cos(a)cos(b) - sin(a)sin(b)
sin(a+b) = sin(a)cos(b) + cos(a)sin(b)
Now, our previous point (X,Y) can be expressed as functions of sine and cosine.
Recalling that cosine is the ratio of the adjacent side to the hypotenuse
(or in our case R) we can calculate X as R*cos(a). Sine is the ratio of the
opposite side to the hypotenuse (still R) so we can calculate Y as R*sin(a).
So... X,Y can be represented as:
X = R*cos(a)
Y = R*sin(a)
Now, using this and the identities - we can calculate Z axis functions for a given angle
as follows:
New_X = R*cos(a+b)
= R*cos(a)*cos(b) - R*sin(a)*sin(b) [care of trig identity]
= X*cos(b) - Y*sin(b) [our formula!]
New_Y = R*sin(a+b)
= R*sin(A)*cos(b) + R*cos(a)*sin(b) [care of trig identity]
= Y*cos(b) + X*sin(b) [our formula!]
That covers off our rotation formula for Z axis rotations, X and Y axis rotations are
quite similar; so I'm not going to define them here. It's far time that we made something
rotate!
1. Our first step is to add our rotation routine.
void RotateZ2d(Vector2d *inPoints,Vector2d *outPoints,int Total,float ang)
{
int i;
for (i=0;i<Total;i++)
{
outPoints[i].x = inPoints[i].x * cos(ang) - inPoints[i].y * sin(ang);
outPoints[i].y = inPoints[i].y * cos(ang) + inPoints[i].x * sin(ang);
}
}
2. We'll add another set of variables to allow us to rotate our points. To make it clear:
We add:
Vector2d lSRTPoints[4]; // Scaled, Rotated, Translated Points
float z_angle; // object rotation
3. We need to initialize our rotation (at the same place that we initialize
x_pos and y_pos).
x_pos=0;
y_pos=0;
scale=1;
z_angle=0; // new
4. Our main render loop changes as follows:
while ((!key[KEY_ESC])&&(!key[KEY_SPACE]))
{
// DO SOMETHING AMAZING HERE!
clear_bitmap(lOffScreen);
// adjust SRT's depending on keys
if (key[KEY_UP]) y_pos++; // TRANSLATE
if (key[KEY_DOWN]) y_pos--;
if (key[KEY_LEFT]) x_pos--;
if (key[KEY_RIGHT]) x_pos++;
if (key[KEY_Q]) scale+=0.1; // scale
if (key[KEY_A]) scale-=0.1;
if (scale<0) scale=0; // prevents scaling with - number
if (key[KEY_W]) z_angle+=0.1; // rotation
if (key[KEY_S]) z_angle-=0.1;
Scale2d(lSquarePoints,lScaledPoints,4,scale); // scale
Translate2d(lScaledPoints,lTranslatedAndScaledPoints,4, //translate
x_pos,y_pos);
RotateZ2d(lTranslatedAndScaledPoints,lSRTPoints,4,z_angle);
DrawScreenCords2d(lOffScreen, lSRTPoints,4,255);
blit(lOffScreen, screen, 0, 0, 0, 0, screen_x, screen_y);
rest(10); // prevents it from flying off the screen too FAST
};
5. Voila! Our w and s keys now rotate our object.
Run the program and see how it behaves. You might be surprised.....
Thou Shalt Pay Attention to the Order of Things (Or Get Weird Results)
The rotating square might surprise you when you run it. I've shown two cubes
in the picture to illustrate what's happening. The problem is that our algorithms are doing
exactly what we've told them... specifically:
1. Scale our Object
2. Translate our Object
3. Rotate our Object
Because we translated our object - our object is no longer centered on the origin.
Our rotation works fine (kind of orbital)... but probably isn't what a user of the program
would expect. Instead... we'd normally expect our object to rotate at its center.
Let's rework the program to do a true SRT:
1. Scale
2. Rotate
3. Translate
Step by step:
1. To prevent confusion, I suggest we change our global variables. In specific:
Vector2d lTranslatedAndScaledPoints[4]; // translated and scaled points
Becomes:
Vector2d lScaledAndRotatedPoints[4]; // Scaled and rotated
2. Our main loop changes slightly... specifically:
Scale2d(lSquarePoints,lScaledPoints,4,scale);
RotateZ2d(lScaledPoints,lScaledAndRotatedPoints,4,z_angle);
Translate2d(lScaledAndRotatedPoints,lSRTPoints,4, x_pos,y_pos);
3. Voila! Now we've got our cube rotating as we'd expect.
You'll notice that the picture shows that our rotation - is now in the center of the object.
Entering the Third Dimension - Perspective and Orthogonal Views "AKA - What to do with Z?".
At this point we are on the cusp of taking things into the third dimension.
We have the math, and the routines to do the graphics; but one question lingers.
"What do we do with Z?" At this point in time, we don't have many three dimensional
displays on the market. So, in truth... three dimensional graphics are never actually
three dimensional. They become flattened by the screen they are projected on.
We need to find a technique to "squish" our mathematics into our flat screen.
The act of squishing our three dimensional object is like creating a projection
of the object. There are two common projection techniques.
1. Parallel Projection:
A Parallel Projection is the simplest projection. Essentially we drop the Z out
of the system all together. This will be our first projection project. The problem
with a parallel projection is that it doesn't care about how far back our objects are.
If a object is 40 units wide, it will take 40 units on the screen no matter how far from
the virtual viewer it lies.
2. Perspective Projection:
A perspective projection is a little more sophisticated. It takes into account or depth
from virtual viewer (situated at the origin), and results in a perspective. This is the
same technique that artists use when painting and sketching. This will be our
second project.
For better understanding, consult the pictures that show a Y / Z oriented view.
The face is looking down the Z axis, centered around the origin. The black line
represents the computer screen - and the curved line shows light being caught by
our virtual eye.
Let's Get Some Three Dimensions!
At this point, we need to extend our square to be a cube - and draw it to the screen.
The simplest thing to do is go back to our wireframe.a.rar, and build our 3d project
from basic principles. We are going to take a basic cube - and allow it to be rotated
with the cursor keys. We'll just do X,Y rotations to illustrate the concepts.
1. We'll start by adding our x_origin and y_origin to the code. I've done this with a
pair of #defines, just under our #define's for sceen_x/screen_y:
#define x_origin_offset 160
#define y_origin_offset 100
2. Our next step is to extend our structure to allow for three dimensional objects.
typedef struct
{
float x;
float y;
float z;
} Vector3d;
3. At this point we need two rotation functions - one for X, the other for Y.
These follow our mathematical formulas:
void Rotate3d_Xaxis(Vector3d *inPoints,Vector3d *outPoints,
int Total, float angleRadians)
{
int i;
for (i=0;i<Total;i++)
{
// X is untransformed, just recopied.
outPoints[i].x = inPoints[i].x;
outPoints[i].y = inPoints[i].y * cos(angleRadians)
- inPoints[i].z * sin(angleRadians);
outPoints[i].z = inPoints[i].y * sin(angleRadians)
+ inPoints[i].z * cos(angleRadians);
}
}
void Rotate3d_Yaxis(Vector3d *inPoints,Vector3d *outPoints,
int Total, float angleRadians)
{
int i;
for (i=0;i<Total;i++)
{
outPoints[i].x = inPoints[i].z * sin(angleRadians)
+ inPoints[i].x * cos(angleRadians);
// Y is untransformed, just recopied.
outPoints[i].y = inPoints[i].y;
outPoints[i].z = inPoints[i].z * cos(angleRadians)
- inPoints[i].x * sin(angleRadians);
}
}
4. Our Draw points routine also changes:
void DrawScreenCords3dParallel(BITMAP *bitmap,Vector3d *inPoints,
int total, int colour)
{
int i;
// draw our shape. Notice this is a closed
// shape, so point a connects to point b,
// point b connects to point c, and
// point c - connects to point a.
for (i=0;i<total;i++)
{
line(bitmap,
(int)(inPoints[i].x+x_origin_offset),
(int)(-inPoints[i].y+y_origin_offset),
(int)(inPoints[(i+1)%total].x+x_origin_offset),
(int)(-inPoints[(i+1)%total].y+y_origin_offset),
255);
}
}
5. We now need to define our cube. It's like a square - but with a lot more points.
You'll notice I'm keeping things simple for our drawing routine and repeating points
for every surface. That means points 0-3 form one surface, 4-7 form the next,
8-11 form the third... etc. This recopies a lot of points (which isn't good),
but is sufficient for showing how things work.
// main constants (more next phase)
Vector3d lCubePoints[24]=
{
{20,20,-20}, {-20,20,-20},{-20,-20,-20},{20,-20,-20}, // font face
{20,20,20}, {-20,20,20}, {-20,-20,20},{20,-20,20}, // back face
{20,20,20}, {20,20,-20}, {-20,20,-20}, {-20,20,20},// top face
{20,-20,20}, {20,-20,-20}, {-20,-20,-20}, {-20,-20,20}, // bottom face
{-20,20,20}, {-20,20,-20}, {-20,-20,-20}, {-20,-20,20}, // left face
{20,20,20}, {20,20,-20}, {20,-20,-20}, {20,-20,20} // right face
}; // cube Points
Vector3d lRotatedPointsX[24]; // rotated cube by X axis
Vector3d lRotatedPointsXY[24]; // rotated cube by X and Y axis
6. We need to add variables to hold our angles. These will be to measure X axis
rotations and Y axis rotations.
float x_angle; // object rotation REMEMBER IN (RADIANS)
float y_angle; // object rotation
7. We also need to initialize these variables:
x_angle=0;
y_angle=0;
8. Last but not least - our main render loop becomes:
while ((!key[KEY_ESC])&&(!key[KEY_SPACE]))
{
// DO SOMETHING AMAZING HERE!
clear_bitmap(lOffScreen);
// adjust SRT's depending on keys
if (key[KEY_UP]) x_angle+=0.5;
if (key[KEY_DOWN]) x_angle-=0.5;
if (key[KEY_LEFT]) y_angle+=0.5;
if (key[KEY_RIGHT]) y_angle-=0.5;
Rotate3d_Xaxis(lCubePoints,lRotatedPointsX,24,x_angle);
Rotate3d_Yaxis(lRotatedPointsX,lRotatedPointsXY,24,y_angle);
for (int i=0;i<24;i+=4)
DrawScreenCords3dParallel(lOffScreen, &lRotatedPointsXY[i],4,255);
blit(lOffScreen, screen, 0, 0, 0, 0, screen_x, screen_y);
rest(10); // prevents it from flying off the screen too FAST
};
9. Voila! That took a few more steps, but you can now enjoy a rotating 3d cube.
You'll notice that the drawing loop is set up to draw surfaces of four vertices each.
If you need to catch up or compare, download wireframe.g.rar.
Let's Get Some Perspective
While it's finally great to see a rotating cube; when you first start the program
with no rotation - all you will see is a square. That's because the first surface
is identical to the second surface in a parallel projection. Now we need to compensate
by adjusting the size of objects that are far away. We do this by centering our world
against the origin. We shrink things that are far away; keeping things nearby unaffected.
Our newly adjusted far away points "converge" on the origin, giving the view perspective.
It's not nearly as hard as it looks.
Imagine how a car simulator works... the road directly ahead looks larger than the road
behind. That's because the road ahead is larger - taking more screen space... then the
road at the end of the horizon. This is the perspective effect we are going to achieve.
The simplest way to achieve the effect is to adjust our X and Y according to the
Z distance. This simply looks like:
Perspective_X = Vertex X / Vertex Z
Perspective_Y = Vertex Y / Vertex Z
Now, this does make some assumptions about our coordinate system. It means that we
are looking from the origin, and that all our world is in +Z values, or is culled
off screen. If we imagined our virtual viewer to be outside the origin (Ie, in -Z),
our geometry would not only flip (upside down), but it would also scale nearby objects
smaller. To avoid this we will assume our geometry is actually in +Z values before
we flip to a perspective view. We aren't quite ready yet however, as we don't yet
know how "deep" our screen should be. If we divide by Z, it's quite possible that
our object will simply shrink away to nothingness.
We get around this by extending our formulas:
Perspective_X = fScale*Vertex X / Vertex Z
Perspective_Y = fScale*Vertex Y / Vertex Z
fScale simply defines how the Z affects our view. Consider like a lens factor.
At this point - we are ready to begin our implementation.
1. First of all - we need to define fScale.
#define fScale 40
2. Since we need to make sure our object exists in positive Z axis,
we push it "back" by translation. Hence we need a translation function,
at least for Z. Here is a generic one.
void Translate3d_XYZ(Vector3d *inPoints,Vector3d *outPoints,int Total,
float x,float y,float z)
{
int i;
for (i=0;i<Total;i++)
{
outPoints[i].x = inPoints[i].x+x;
outPoints[i].y = inPoints[i].y+y;
outPoints[i].z = inPoints[i].z+z;
}
}
3. We need a place to store our translated points... so we add new variable.
Vector3d lRotatedPointsXY_Translated[24]; // rotated then translated
4. Our last transformation is to push the object backwards, and call our
new drawing routine (which we will soon write):
// Translate the object 40 units forward to force Z into positive units
Translate3d_XYZ(lRotatedPointsXY,lRotatedPointsXY_Translated,24,0,0,40);
for (int i=0;i<24;i+=4)
DrawScreenCords3dPerspective(lOffScreen, &lRotatedPointsXY_Translated[i],4,255);
5. And now - we need to add our drawing routine, which looks like our formulas:
// converts mathematical ponts to screen points and plots them. (PERSPECTIVE)
void DrawScreenCords3dPerspective(BITMAP *bitmap,Vector3d *inPoints,int total,
int colour)
{
int i;
// draw our shape. Notice this is a closed shape, so point a connects to
// point b, point b connects to point c, and point c - connects to point a.
for (i=0;i<total;i++)
{
line(bitmap,
(int)(fScale*inPoints[i].x/inPoints[i].z+x_origin_offset),
(int)(fScale*-inPoints[i].y/inPoints[i].z+y_origin_offset),
(int)(fScale*inPoints[(i+1)%total].x/inPoints[(i+1)%total].z
+x_origin_offset),
(int)(fScale*-inPoints[(i+1)%total].y/inPoints[(i+1)%total].z
+y_origin_offset),255);
}
}
6. Voila! We now have a rotating cube with perspective. It looks a bit odd
from time to time - but mostly that's relating to the view scale etc... feel free
to adjust the cube size / fScale to get things right for your application.
Object Hierarchies
At this point we've exposed all the mathematics required to do basic Wireframe graphics.
There obviously is quite a difference between a cube and a complicated object however - and
I want to discuss some of that now. Objects are rarely in isolation. Animating a
simple car would require moving both the wheels - and the frame of the car.
Animating a helicopter is the same idea - the rotor moves around; but it's attached
to the cockpit. Usually we create a chain of SRT transformations to adjust objects
from being in "object space" or "model space", to their final position in world space.
In a simple example:
1. We rotate the rotor of a helicopter (rotation along the Y axis). The rotor is centered around the origin.
2. We translate the rotor upwards (according to the height of the cockpit). This means the object can be rendered along side the cockpit and it will "match".
3. We perform any SRT to both the adjusted (rotated / and translated) rotor, as well as the cockpit. This allows us to place the completed helicopter anywhere we want into three dimensional space.
The concepts for a simple helicopter extend to all objects that have relationships.
These types of spatial relationships are known as an object hierarchy. The most useful
area to use an object hierarchy is in character animation. You might start at the torso,
add an upper arm, add a fore arm, add a hand (with wrist), add each finger - each with
3 segments. Once we get to render the end of the finger - we will have passed through
six joints - and possibly six unique SRT transformations. We need to consider both
the orientation of the joint, as well as how and where the bone will connect.
The problem however - is that at a certain point we get overwhelmed by all
our transformations. Wouldn't it be nicer if there was an intelligent way to group
a series of transformations - into a single unit? There is a better way...
called Matrices.
Enter the Matrix!
The ultimate goal of any real time computer graphics is to render to the screen
as quickly as possible. While we've defined our transformations, it's easy for them
to get unruly, in both complexity and calculation time. Matrices give us a way
to reduce the number of calculations performed - while simplifying our work, and improving
calculation speed. It's possible to have a single matrix represent a X translation,
a Y translation, a Z translation, Scaling X, Scaling Y, Scaling Z, Rotation in X, Rotation
in Y and Rotation in Z!!! Talk about one stop shopping!
It gets even better. Not only can we represent a series of transformations into
a matrix - but we can also perform operations on matrices. So, if we have a matrix
that performs a Scaling, but we also want to do rotations - we can combine these
two matrices using Matrix Arithmetic. We get a new matrix which does not only
the scaling but also the rotation. Computers equipped with MMX or SIMD type systems
are especially suited for matrix applications. Direct X includes a library of
matrix functions in D3DX - which are optimized to work very efficiently on any cpu.
However, for now we'll code them ourselves to get you used to the idea of matrices.
Show me the Matrix!
Matrices are a generic concept in mathematics, and matrix is just another word
for a table of numbers. Matrices can be any size - and shape (they don't have to
be a flat table either). Computer graphics use a simple matrix (only 4 rows by 4 columns),
for a total of 16 values. A simple matrix for computer graphics could appear as follows:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Remember that matrices aren't limited to being square or 4x4. It's just as possible
to have a matrix with just one row. A set of 3d points (x,y,z) - could be stored
in a 1x3 matrix. A 1x3 matrix is also called a vector, which is very useful because
it's a "point" in our three dimensional space. Now, assuming that we have a matrix
(grid of numbers) and a vector... how do we find out our new x,y,z? We use matrix
multiplication to calculate a new vector.
New VectorX,Y,Z = Old Vector X,Y,Z * Matrix
Please realize that this isn't your standard multiplication that you learned in
grade school. This is matrix multiplication, which defines the shape of the
resulting matrix (how many columns and rows), and how to map between your two
input matrices and create a resulting matrix. It's not nearly as complicated as
it sounds. It turns out that when matrix multiplication was defined, it was defined
with a restriction. You can only multiply matrices if the number of columns of the
first matrix is the same as the number of rows of the second matrix. Do you notice
a problem?
I've told you that you can represent SRT transformations in a 4x4 matrix,
but we need to use matrix multiplication to calculate the results of a 3 element vector.
A three element vector only has 3 columns, which is one shy of the required 4 columns.
How do we get around this? Easy - we use the simplest trick in the book and
fudge the numbers. To get our resulting transformation, we add an extra element.
New Vector <X,Y,Z, ignored> = Old Vector <x,y,z,ignored> * Matrix.
We'll set the ignored value to one so it doesn't affect our calculations.
It will be used in the matrix calculations - but ultimately thrown away.
We can craft specific vector instructions to drop them out at the start - but either way..
they don't get used.
So, what does matrix multiplication look like? Let's say we are multiplying two
matrices - A and B. We know that A has the same number of columns - as the number
of rows of B. This is essential to our mapping. We map the columns of A - to the rows
in B.
Here I've plotted two matrices. A is a 2x4 matrix. B is a 4 by 3 matrix.
The number of columns in A is 4, and the number of rows in B is also 4.
So we know we can multiply these two matrices. I've put boxes around the matrices so
you can tell which belong together.
I've labeled the entries in our matrix as A?* - where ? is the row, and * is the column.
Similarly, I've done the same with Matrix B, and Matrix R - our resulting matrix.
If Matrix A is a MxN matrix (M rows by N columns) and Matrix B is a NxP matrix
(N rows by P columns) we get a MxP matrix. IE, Matrix R will have the same number
of rows as Matrix A, and the same number of columns as matrix B.
To calculate our result, we multiply according to the intersection of rows and columns
in A and B. For example: R11 is the result of multiplying matrix A's first row, and
Matrix B's first column. R21 is the result of multiplying the second row of Matrix A
and the First row of Matrix B. It's like looking up the timetable of the bus.
Every square in the result section, depends on the matrix A values on its left, and
the Matrix B values on the right. We still haven't said how it depends - but that's
the easy part.
Each R is calculated as the sum of A values multiplied by B values. For example:
R22 = A21*B12 + A22 * B22 + A32 * B32 + A23 * B42
You can trace your fingers along this path. You start with A21, and B12.
These two multiply. We then move on to the next square, A22 and B22.
These multiply and are added to our series. So on and so forth - until we've done
the calculation. We can easily write some for loops to do this transformation.
Mathematically it's expressed in summation notation which this looks like the following:
To solidify our understanding, let's multiply a 1x4 vector against a 4x4 matrix
R11 = A11*B11 + A12*B21 + A13*B31 + A14*B41
R12 = A11*B12 + A12*B22 + A13*B32 + A14*B42
R13 = A11*B13 + A12*B23 + A13*B33 + A14*B43
R14 = A11*B14 + A12*B24 + A13*B34 + A14*B44
That gives us our mathematics to express our vector * matrix multiplication.
Let's express the same thing in code. Vector is our inbound vector (integer [4]),
our result vector is called result (integer[4]), and matrix is our transformation matrix
(integer[4][4]). The code unrolled looks as follows:
result[0]=vector[0]*matrix[0][0] + vector[1]*matrix[1][0] + vector[2]*matrix[2][0] + vector[3]*matrix[3][0];
result[1]=vector[1]*matrix[0][1] + vector[1]*matrix[1][1] + vector[2]*matrix[2][1] + vector[3]*matrix[3][1];
result[2]=vector[2]*matrix[0][2] + vector[1]*matrix[1][2] + vector[2]*matrix[2][2] + vector[3]*matrix[3][2];
result[3]=vector[3]*matrix[0][3] + vector[1]*matrix[1][3] + vector[2]*matrix[2][3] + vector[3]*matrix[3][3];
We can of course roll this up - it looks a bit neater like this
(but isn't quite as fast because of the for loop taking some extra code):
int i;
for (i=0;i<4;i++)
{
result[i]=vector[i]*matrix[0][i] + vector[1]*matrix[1][i]
+ vector[2]*matrix[2][i] + vector[3]*matrix[3][i];
}
We can role it up even further - but I think you get the idea. In review so far - we've
shown that points <x,y,z> can be expressed as a 1x4 matrix. We've illustrated that
matrices can be multiplied by vectors to transform the vector. We can scale a vector
by multiplying it by a scaling Matrix. We can rotate vectors by rotating it by a
rotating matrix. I haven't yet shown what those matrices look like - that's the next
step. The one thing I want you to learn is this: We don't just use matrix multiplication
(also called concatenation) to calculate the result of vectors transformed by a matrix.
We use it to multiply matrices together.... concatenating matrices.
For example:
Matrix A == Scaling Matrix
Matrix B == Rotating Matrix
Matrix C == Matrix A * Matrix B == A matrix that scales and then rotates.
In code, the concatenation of two 4x4 matrices appears as follows:
(just one implementation)
C=A*B
for (int i=0; i<4; i++)
for (int j=0; j<4; j++)
{
C[i][j]=0; // init output matrix
for (int k; k<4; k++)
C[i][j]+=A[k][j]*B[k][j];
}
It's generic matrix multiplication that allows us to combine all our crazy transformations
into a single matrix package. That's what all this fuss (and work) is about.
SRT Matrices
It's high time now that we looked at the transformation matrices that we can use to
apply SRT - scaling, rotation and translation. Remember all of these are 4x4 Matrices,
and when multiplied by a 1x4 vector result in the operation being performed against that
vector. The matrices can be combined to create a "combined transformation matrix".
Let's define all our SRT matrices:
Scales by scale_x, scale_y, scale_z. Notice if scale_x=1, scale_y=1, and scale_z=1 we
get a matrix that doesn't affect the geometry. This is called an identity matrix,
as any matrix * Identity = the same matrix. Identity matrices can be easily recognized
as they have zero for all values except the diagonal - (top left to bottom right) which is
set to one.
This translates our vector by trans_x, trans_y, and trans_z. You might notice that we
could easily add scaling too - by replacing the first few 1's (diagonal) with
scale_x, scale_y, and scale_z. Just remember, that as we re-use cells in our matrix
it can be more difficult to overlaying another matrix to combine them. To combine matrices
into a single transformation - multiply them out! (Concatenate them!)
Implementing - The Matrix
Our last project will be to implement some matrix arithmetic into the works.
Ideal in terms of operations (and simplifying the math), we'd collect up our
transformations and multiply them out. This will create a new matrix that we'll use
to transform the object any way we please. In practice, the computer is fast at
multiplying out matrices (using SIMD type operations)... and usually transformations
are composed using the graphics api rather than manually working them out. We'll
do that here too - so we can easily flow into that model of doing things later.
(I want you to understand the nuances of using matrices, you can optimize the hell
out of it later.)
Our first step will be to introduce some new functions: Specifically, functions to
multiply matrices, vectors, and do rotation and translations.
/*----------------------------------------------------------------------------*/
// mat R == result matrix
void MultiplyMatrix(float matR[4][4], float matA[4][4], float matB[4][4])
{ // no optimizations here
for (int i=0;i<4;i++)
{
for (int j=0;j<4;j++)
{
matR[i][j]=0;
for (int k=0;k<4;k++)
{
matR[i][j]+=matA[i][k]*matB[k][j];
}
}
}
}
/*----------------------------------------------------------------------------*/
void MultiplyVectors(Vector3d *inPoints,Vector3d *outPoints,int Total,
float mat[4][4])
{
int i;
// somewhat streamlined matrix * vect function
for (i=0;i<Total;i++)
{
// copy result out.
outPoints[i].x=
inPoints[i].x*mat[0][0] +
inPoints[i].y*mat[1][0] +
inPoints[i].z*mat[2][0] +
mat[3][0]; // (1 fudge)
outPoints[i].y=
inPoints[i].x*mat[0][1] +
inPoints[i].y*mat[1][1] +
inPoints[i].z*mat[2][1] +
mat[3][1]; // 1 fudge
outPoints[i].z=
inPoints[i].x*mat[0][2] +
inPoints[i].y*mat[1][2] +
inPoints[i].z*mat[2][2] +
mat[3][2]; // 1 fudge
}
}
/*----------------------------------------------------------------------------*/
// creates a translation matrix for x,y,z translation
void TranslationMatrix(float matR[4][4],float x,float y,float z)
{
// clear matrix;
int i,j;
for (i=0;i<4;i++)
for (j=0;j<4;j++)
{
if (i==j)
matR[i][j]=1;
else
matR[i][j]=0;
}
// at this point we have an identity matrix
// fill in the other values
matR[3][0]=x;
matR[3][1]=y;
matR[3][2]=z;
}
/*----------------------------------------------------------------------------*/
void RotateYMatrix(float matR[4][4],float y_angle)
{
// clear matrix;
int i,j;
for (i=0;i<4;i++)
for (j=0;j<4;j++)
{
if (i==j)
matR[i][j]=1;
else
matR[i][j]=0;
}
// at this point we have an identity matrix
// fill in the other values
matR[0][0]= cos(y_angle);
matR[0][2]= -sin(y_angle);
matR[2][0]= sin(y_angle);
matR[2][2]= cos(y_angle);
}
/*----------------------------------------------------------------------------*/
void RotateXMatrix(float matR[4][4],float x_angle)
{
// clear matrix;
int i,j;
for (i=0;i<4;i++)
for (j=0;j<4;j++)
{
if (i==j)
matR[i][j]=1;
else
matR[i][j]=0;
}
// at this point we have an identity matrix
// fill in the other values
matR[1][1]= cos(x_angle);
matR[1][2]= sin(x_angle);
matR[2][1]= -sin(x_angle);
matR[2][2]= cos(x_angle);
}
Our main program changes now... to use mostly matrices instead of vector lists.
These include:
float XrotMat[4][4]; // X rotation Matrix
float YrotMat[4][4]; // Y rotation Matrix
float TransMat[4][4]; // translation Matrix
float XYRotMat[4][4]; // X rotation, Y rotation
float World[4][4]; // X,Y rotation + Translation
// (combined into a world matrix)
Vector3d renderPoints[24]; // points to render
The guts of our render loop also change:
// compose our X rotation and Y rotation matrices
RotateXMatrix(XrotMat,x_angle);
RotateYMatrix(YrotMat,y_angle);
// Set up Translation matrix (notice since it's constant we don't
// need to calc!)
TranslationMatrix(TransMat,0,0,40);
MultiplyMatrix(XYRotMat,XrotMat,YrotMat);
MultiplyMatrix(World,XYRotMat,TransMat); // rotate , then translate
// multiply our points
MultiplyVectors(lCubePoints,renderPoints,24,World);
for (int i=0;i<24;i+=4)
DrawScreenCords3dPerspective(lOffScreen, &renderPoints[i],4,255);
Voila! You are now rendering with matrices. This is less efficient in our
contrived example of only a cube, but on the whole in a large examples this will be
more efficient. If you got lost along the way - catch up with wireframe.i.rar.
The end of the Matrix?
Well, not exactly. We've only scratched the surface of what's available.
Later on we'll dig into Direct X and/or Open GL -> and we'll use the d3dx functions
to do our matrix math. However, having coded and mastered this - you've got an
unbeatable understanding of matrices.
For those wishing to pursue further - do some searching for "matrix stacks".
They are very useful for object hierarchies, and are built into Open GL (natively),
and direct x (as part of the d3dx library).
In addition for an extra challenge - you might examine ways to prevent from
duplicating vertices. There are two things to look for about this:
1. Triangle fans and strips (a way of representing a shape while reducing the number
of duplicated vertices).
2. Vertex indexing ;-).
Coming Soon!
Well folks, as promised - I respond to reader requests. I haven't decided what's
next..... but I'm already looking forward to it.
Will it be a:
1. Extension on our Wireframe graphics?
2. Scrollers 201? Working towards a scroller generation program?
3. Or something completely different?
Don't forget to cast your vote and email me at: polaris@northerndragons.ca.
In the mean time - take care!
Polaris